package array.medium;

import java.util.Arrays;

/**
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 */
public class findKthLargest {

    public static void main(String[] args) {
        int[] test = {3, 4, 2, 1, 5, 6, 4};
        System.out.println(myCode1(test, 2));
        System.out.println(myCode2(test, 2));
        int a = 0;
    }

    /**
     * 第一时间想到的方法，将数组从大到小排序，然后取第k-1个元素
     * 我感觉是考察排序
     * 这种方法时间复杂度比较高
     * @param nums
     * @param k
     * @return
     */
    public static int myCode(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (nums[i] < nums[j]) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        return nums[k - 1];
    }

    /**
     * stream一行代码方式
     * @param nums
     * @param k
     * @return
     */
    public static int myCode1(int[] nums, int k) {
        /**
         * 这个方法使用了快速排序法
         */
        Arrays.sort(nums);
        return nums[nums.length - k];
//        return Arrays.stream(nums).sorted().toArray()[nums.length - k];
    }

    /**
     * 调用快速排序法
     * @param nums
     * @param k
     * @return
     */
    public static int myCode2(int[] nums, int k) {
        quickSort(nums, 0, nums.length - 1);
        return nums[nums.length - k];
    }

    /**
     * 快速排序法
     * 1．先从数列中取出一个数作为基准数。
     * 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
     * 3．再对左右区间重复第二步，直到各区间只有一个数。
     */

    /**
     * 挖坑排序，在数组中选定一个基准数，将它保存在变量中
     * 这样数组中就有一个位置可以赋值为其他值
     * 需要将比基准数小的数放在其左边，反之放在其右边
     * 参数l代表左指针的位置，r代表右指针的位置
     * 如果要使用数组的第一个元素为基准数，那么首先右指针开始移动，找到一个比基准数小的数，放在基准数位置
     * 举例说明：nums[3, 4, 2, 1, 5, 6, 4]
     * 选择3为基准数，此时左指针指向nums[0],右指针指向nums[6]
     * 首先判断当前右指针指向的元素是否小于3,不小于,右指针向左移动,重复判断,直到找到小于基准数的元素.当右指针移动时,就代表指针指向的元素大于基准数
     * 当右指针指向nums[3]时,满足元素小于3,把nums[3]移动到左指针指向的位置,此时左指针指向的元素已经小于基准数了,所以此时将左指针移动一位
     * 移动后:[1, 4, 2, 1, 5, 6, 4].移动后nums[3]的元素又可以改变了.
     * 此时左指针移动,找到大于基准数的元素,当右指针指向nums[1]时,满足当前元素大于基准数,将右指针指向的元素移动到左指针指向的位置,同理此时右指针指向的元素已经大于基准数了,所以此时将右指针移动一位
     * 移动后:[1, 4, 2, 4, 5, 6, 4]
     * 此时右指针指向的元素可以改变了,左右指针未重合,重复以上动作.
     * 左指针移动找到比基准数小的,移动
     * 右指针移动找比基准数大的,移动
     * 循环结束:[1, 2, 2, 4, 5, 6, 4]
     * 此时左右指针重合,都指向nums[2],此时将基准数放在这个元素上
     * 最终:[1, 2, 3, 4, 5, 6, 4]
     * 基准数的左边小于它,右边大于它
     * 注意:时刻保证左指针小于右指针
     * @param s
     * @return
     */
    public static int AdjustArray(int[] s, int l, int r) {
        int i = l, j = r;
        int temp = s[i];
        while (i < j) {
            while (i < j && s[j] >= temp) {
                j--;
            }
            if (i < j) {
                s[i++] = s[j];
            }

            while (i < j && s[i] <= temp) {
                i++;
            }
            if (i < j) {
                s[j--] = s[i];
            }
        }

        s[i] = temp;
        return i;
    }

    /**
     * 在经过上面的排序后,数组为[1, 2, 3, 4, 5, 6, 4]
     * 只是将基准数左侧都小于它,右侧都大于它,并不是完全排序好的状态
     * 此时只需要利用分治思想,将基准数的左和右侧看为两个新的数组,递归调用排序方法就可以了
     * int[] s, int l, int r
     * 将上面的方法改为返回此次调用后基准数的指针
     */
    public static void quickSort(int[] s, int l, int r) {
        if (l < r) {
            int i = AdjustArray(s, l, r);
            // 左侧数组调用
            quickSort(s, l, i - 1);
            // 右侧数组调用
            quickSort(s, i + 1, r);
        }
    }

}
